Méthodes basées sur la programmation dynamique

Dans le cadre de l'apprentissage par renforcement, l'utilisation de méthodes de programmation dynamiques permet de calculer les solutions des fonctions de valeurs d'états et d'actions optimales. Cela nous permettra de déterminer par la suite la stratégie que l'agent doit suivre.

Ces méthodes fonctionnent lorsque:

• Le MDP possède un nombre fini et restreint d'états
• Le modèle de l'environnement est parfaitement connu

Nous allons étudier deux algorithmes qui sont:

• L'algorithme par itération des stratégies (Policy Iteration). Cet algorithme comprend deux étapes principales:

  • L'évaluation d'une stratégie (Policy Evaluation)
  • L'amélioration d'une stratégue (Policy Improvement)

• L'algorithme par itération des valeurs (Values Iteration).

4. Algorithme par itération des stratégies

4.1. Évaluation d'une stratégie

Pour commencer, nous avons besoin de pouvoir évaluer certaines stratégies que l'agent met en place. On a vu précédemment qu'une stratégie $\pi$ est meilleure qu'une stratégie $\pi'$ si le gain obtenu en suivant cette stratégie est supérieur ou égal à celui obtenu en suivant la stratégie $\pi'$, et cela pour l'ensemble des états de l'environnement. Pour mettre ce concept en pratique et pouvoir comparer des stratégies, il nous faut donc une méthode qui permet d'évaluer une stratégie arbitraire. C'est le but de l'algorithme d'évaluation des stratégies.

L'algorithme d'évaluation des stratégies se base sur l'estimation de la fonction des valeurs d'états d'une stratégie arbitraire $\pi$:

$${V_\pi }\left( s \right) = \sum\limits_a {\pi \left( {a|s} \right)\sum\limits_{s'} {\sum\limits_r {p\left( {s',r|s,a} \right)} } } \left[ {r + \gamma {V_\pi }\left( {s'} \right)} \right]$$

où $\pi(a|s)$ est la probabilité que l'agent prenne l'action $a$ lorsqu'il est dans l'état $s$ et lorsqu'il suit la stratégie $\pi$.

L'existence et l'unicité de $V_\pi$ sont garantis si $\gamma < 1$ ou si un état terminal est atteint quelque soit l'état de départ $s$ en suivant la stratégie $\pi$.

Si la dynamique de l'environnement est parfaitement connue, alors les solutions de l'équation précédente sont les solutions d'un système d'équations à $|S|$ inconnues (les $V_\pi(s)$, $s\in S$). Pour résoudre ce problème de manière itérative, on considère une séquence de fonctions de valeurs d'états $v_0, v_1, v_2, ...$ L'approximation initiale $v_0$ est choisie de manière aléatoire (la seule condition est que la valeur de l'état terminal doit être nulle), et chaque approximation successive est obtenue en utilisant l'équation de Bellman pour $V_\pi$ en suivant la procédure de mise à jour suivante:

$${V_{k + 1}}\left( s \right) = \sum\limits_a {\pi \left( {a|s} \right)\sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma {V_k}\left( {s'} \right)} \right]} }$$

Il est clair que $V_k = V_\pi$ est un point fixe de cette règle de mise à jour su fait de l'existence et de l'unicité de $V_\pi$. On montre que cette séquence converge vers $V_\pi$ lorsque $k \to \infty$ sous ces mêmes conditions. Cet algorithme est appelé algorithme d'évaluation itératif des stratégies.

Pour obtenir chaque itération successive, $V_{k+1}$ depuis $V_k$, cet algorithme effectue le même calcul pour chaque état: il remplace l'ancienne valeur de l'état $s$ par une nouvelle valeur obtenue à partir des anciennes valeurs des états suivants de l'état $s$ et de la récompense immédiate, en suivant toutes les possibilités qui découlent de l'application de la stratégie qui est évaluée. Chaque itération de cet algorithme met à jour la valeur de chaque états de l'environnement pour produire une nouvelle fonction de valeurs d'états $V_{k+1}$.

Exemple

On considère l'environnement ci-dessous, dans lequel l'agent peut effectuer les actions $A = \left\{ {haut,bas,droite,gauche} \right\}$. Les probabilités $\pi(a|s)$ sont déterministes et les probabilités de transition sont équiprobables. La récompense est de $R_t=-1$ pour toutes les transitions. L'état terminal est grisé sur la figure (bien qu'il apparaisse à deux endroits, c'est en fait un seul et même état). Si une action prise fait sortir l'agent de la grille, alors son état reste inchangé.

La figure ci-dessous montrent la séquence des fonctions de valeurs d'états $V_k$ obtenues lors des itérations de l'algorithme d'évaluation des stratégies. La dernière estimation est en fait $V_\pi$.

Pour déterminer si l'algorithme a convergé vers une solution, il est nécessaire de mettre en place un test. Chaque fois que la nouvelle fonction de valeurs des états est calculée, l'algorithme calcule la somme des valeurs des états et compare cette somme avec elle effectuée lors de l'itération précédente. Si la différence entre les deux sommes est inférieure à un seuil fixé, alors l'algorithme prend fin. La figure ci-dessous illustre ce concept:

4.2. Algorithme